#include <cstdio>
#include <cstdlib>
#include "../01-preface/Status.h"

#define MaxSize 100

/*
 * 顺序表
 */
//静态分配
typedef struct {
    int data[MaxSize];
    int length;
} SqList;
//动态分配
#define LIST_INIT_SIZE 50
#define LISTINCREMENT 10
typedef struct {
    int *elem; // 存储空间基址
    int length; // 当前长度
    int listsize; // 当前分配的存储容量（以sizeof(ElemType)为单位
} SeqList; // 动态分配数组循序表的类型定义

bool InitList(SqList &L) {
    L.length == 0;
    return true;
}

// 动态分配初始化
//Status InitList_Sq(SeqList &L) {
//    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
//    if (!L.elem) exit(OVERFLOW); // 分配失败
//    L.length = 0; // 空表长度为0
//    L.listsize = LIST_INIT_SIZE; // 初始存储容量
//    return OK;
//};

bool ListInsert_Sq(SqList &L, int i, int e) {
    // 在顺序表L中第i个位置上插入元素e
    if (i < 1 || i > L.length + 1) return false;  // 插入位置不合法
    if (L.length + 1 > MaxSize) return false; // 数组长度越界
    for (int j = L.length; j >= i; i++) {
        L.data[j] = L.data[j - 1];  // 1. 插入位置之后的元素后移一位
    }
    L.data[i - 1] = e;  // 2. 插入元素
    L.length++;  // 3. 表长加一
    return true;
}


bool ListDelete_Sq(SqList &L, int i, int &e) {
    // 删除顺序表中第i个位置上的元素， 并用e返回删除元素的值
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];  // 1. 保存删除元素的值
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];  // 2. 删除位置之后的元素前移一位
    }
    L.length--;  // 3. 表长减一
    return true;
}

bool Locate_Sq(SqList L, int i, int &e) {
    // 查找第i个位置上的元素的值,并用e返回
    if (i < L.length || i > L.length) return false;
    e = L.data[i - 1];
    return true;
}

bool Empty_Sq(SqList L) {
    if (L.length == 0)
        return true;
    return false;
}

/*
 * 链表
 */
typedef struct LNode {
    int data;  // 数据域
    struct LNode *next; // 指针域
} LNode, *LinkList;   // 单链表结构体

typedef struct DLNode {
    int data;  // 数据域
    struct DLNode *prior, *next;  // 前驱指针和后继指针
} DLNode, *DLinkList;  // 双链表结构体


bool ListInit_Link(LinkList &L) {
    // 初始化单链表
    L = (LNode *) malloc(sizeof(LNode));
    if (!L) return false;
    L->next = NULL;
    return true;
}

int ListLength(LinkList L) {
//    L为带头结点的单链表，输出L的长度
    int k = 0; // 计数器
    LNode *p;  // 遍历指针，初始化指向第一个元素节点
    p = L->next;
    while (p) {
        k++;
        p = p->next;
    }
    return k;
}


bool ListInsert_Link(LinkList &L, int i, int e) {
    // L是带头结点的单链表，在第i个位置前插入元素e（一般的插入）
    LNode *p, *s;
    int j = 0;
    p = L;
    while (p->next && j < i - 1) {  // 查找到第i-1个元素的位置
        j++;
        p = p->next;
    }
    if (!p || j > i - 1) return false; // 插入位置不合法
    s = (LNode *) malloc(sizeof(LNode));  // 申请一个节点用来记录e
    if (!s) return false;
    s->data = e;  // 保存e的值到s的数据域
    s->next = p->next;  // 修改s的指针域
    p->next = s; // 修改s的指针域
    return true;
}

bool ListDelete_Link(LinkList &L, int i, int &e) {
    // L为带有头结点的单链表的头指针
    // 删除单链表中第i个元素，并用e返回其值
    LNode *p = L, *q;
    int j = 0;
    while (p->next && j < i - 1) {  // 寻找第i-1个结点，并让p指向此结点
        p = p->next;
        j++;
    }
    if(!p->next || j>i-1) return false; // 删除位置不合理
    q = p->next;  // 删除并释放结点
    p->next = q->next;
    e = q->data;
    free(q);
    return true;
}

void CreateList_L_Rear(LinkList &L, ElemType a[], int n) {
    // 已知一维数组A[n]中存有线性表的数据元素，利用尾插法创建单链表L
    LinkList p, q;
    int i;
    L = (LNode *) malloc(sizeof(LNode));   // 创建头结点
    q = L;  // q始终指向尾结点，开始时尾结点也是头结点
    for (i = 0; i < n; i++) {
        p = (LinkList) malloc(sizeof(LNode));  // 创建新结点
        p->data = a[i];  // 赋值
        q->next = p;   // 插入在尾结点之后
        q = p;  // q指向新的表尾
    }
    q->next = NULL;  // 表尾结点指针域置空
}

void CreateList_L_Front(LinkList &L, ElemType a[], int n) {
    // 已知一维数组A[n]中存有线性表的数据元素，利用头插法创建单链表L
    LinkList p;
    L = (LNode *) malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = n - 1; i >= 0; i--) {
        p = (LNode *) malloc(sizeof(LNode));
        p->data = a[i];
        p->next = L->next;  // 插入在头结点和第一个结点之间
        L->next = p;
    }
}

LNode *LocateElem_L(LinkList L, ElemType e) {
    // 在L所指向的单链表中查找第一个值和e相等的结点，若存在，则返回其指针
    LinkList p;
    p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}

Status GetElem_L(LinkList L, int i, ElemType &e) {
    // L为带头结点的单链表的头指针
    // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    LinkList p;
    int j = 1;  // 声明一个计数器
    p = L->next; // 初始化p指向第一个结点
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (j != i) return ERROR;  // 第i个元素不存在
    e = p->data;  // 取第i个元素
    return OK;
}

int main() {

    return 0;
}